In a data switching network, data traffic is categorized into various flows which are stored in a number of queues in a buffer. In a router or other network element, the stored queues typically compete for a common outgoing communications link or egress port (e.g., a physical communications link or a pseudo-wire). Thus, the buffered queues need to be scheduled on the egress side. Accordingly, processing is required by token scheduling devices on the egress side in the router prior to transmission performed to select which of the queued packets will be the next in line for outgoing transmission.
Typically, in a routing process, tokens of data coming from different source ports are classified based on their source and destination ports, and traffic types. They are subsequently sorted into different queues in the buffer. The tokens of data that pass through a router network and/or are processed by a router network are maintained, at least temporarily, in a buffer memory. Typically, a memory data structure known as a linked list queue is maintained in association with the buffer memory. A linked list queue contains a list of pointers respectively pointing to each memory location in the buffer memory in which data associated with each token is stored. A conventional queue structure typically stores, in one continuous, sequential list, each pointer associated with each token of data that is currently stored in the buffer memory. The state of each queue is updated and related link-list pointers are updated when a token of data enters into the queue. Based on the output port availability, the scheduler selects a scheduling algorithm to dequeue the tokens of data from the queues. The state of each queue and linked list pointers will be then be updated again when a token of data moves out of a queue.
Additional latency time is incurred in the processing of multicast traffic data packets as steps of classifying tokens of data are required and are based on the source and destination ports and traffic types. Initially, the tokens of data associated with the data packets are sorted into different queues and then upon entry into a queue, the state of the queue is updated. Next, based on port availability, a scheduler selects a scheduling algorithm to dequeue the tokens from corresponding queues in the buffer memory. This step of waiting for port availability has to be repeated for each of the tokens of data to be sent. Also, Quality of Service (QoS) algorithmic checks are required if copies of the tokens of data are required to be replicated and sent to additional ports. Further, sometimes additional checks are necessary when transmitting the tokens of data when guarantee of preferential service is needed for, as an example, high priority traffic, such as control traffic or voice/video latency sensitive traffic. Such checks can generate additional latency time during transmission.
The buffer manager's performance is limited by the pipeline flow of the tokens of data in the enqueue and dequeue processing operations. When the buffer is full, the buffer manager must wait until a token of data is dequeued before enqueuing additional tokens of data. In order to reduce the latency time here, parallel buffers are introduced to enable additional tokens of data to be enqueued. However, such additional parallel buffers use additional resources and processing power. Additionally, each time the buffer memory is to be processed in some operation performed by the router, the queue must be accessed or addressed such that the pointer associated with that token of data is obtained.
As processing speeds associated with routers or other packet switches increase (e.g., 10 gigabits per second and faster), the input and output bandwidth and access latency associated with the memory used to maintain the queue becomes critical. That is, given the fact that a conventional queue must be accessed each and every time a token pointer is needed, the queue memory can become a significant bottleneck.